\section{整除的概念}


\begin{frame}{带余除法}
这一节以及后面各节的讨论都是在某一个固定的数域 $P$ 上的多项式环 $P[x]$ 中进行的，以后就不每次重复说明了。

\pause
在一元多项式环中，可以做加、减、乘三种运算， 但是乘法的逆运算——除法并不是普遍可以做的。因之整除就成了两个多项式之间的一种特殊的关系。

\pause
和中学中所学代数一样， 作为形式表达式， 也能用一个多项式去除另一个多项式，求得商和余式。
\pause
例如，设
\[
f=3 x^{3}+4 x^{2}-5 x+6, \quad g=x^{2}-3 x+1 .
\]
\pause
我们用 $g$ 去除 $f$,可以按下面的格式来做除法（称为\emph{长除法}）：
\setlength{\tabcolsep}{2pt}
\[
  \begin{tabular}{R|RRRR|L}
    x^2-3x+1 & 3 x^{3} & +4 x^{2}& -5 x & +6  & 3x+13 \\
    & 3 x^{3}& -9 x^{2} & +3 x & & \\
    \cline{2-5}
    & & 13x^2& -8x& +6 & \\
    & & 13x^2& -39x & +13 & \\
    \cline{2-5}
    & & & 31x& -7
  \end{tabular}
\]
\pause
于是求得商为 $3 x+13$, 余式为 $31 x-7$. 所得结果可以写成
\[
3 x^{3}+4 x^{2}-5 x+6=(3 x+13)\left(x^{2}-3 x+1\right)+(31 x-7).
\]
\pause
这个求法实际上具有一般性。下面就按这个想法来证明一元多项式环的一个基本性质。
\end{frame}



\begin{frame}
  \begin{proposition*}[带余除法]
    对于 $P[x]$ 中任意两个多项式 $f$ 与 $g$, 其中 $g \neq 0$, 一定有 $P[x]$ 中的多项式 $q, r$ 存在，使
    \begin{equation*}
    f=q g+r \tag{1}
\end{equation*}
成立， 其中 $\partial(r)<\partial(g)$ 或者 $r=0$, 并且这样的 $q, r$ 是唯一决定的。
\end{proposition*}
\pause
带余除法中所得的 $q$ 通常称为 $g$ 除 $f$ 的\emph{商式}， $r$ 称为 $g$ 除 $f$ 的\emph{余式}，简称\emph{商}及\emph{余}。
\pause
\begin{proof}
  先证所要求的$q,r$的存在性。$f=0$的情形平凡，故设$f\neq 0$.
  我们对$\partial f$归纳。
  \pause
  若$\partial f<\partial g$, 令$q=0, r=f$即可。
  \pause
  现在考虑$\partial f=n\geqslant \partial g=m$. 
  \pause
  为了能做归纳，我们通过$g$的首项来消$f$的首项。设
  \[
    f=a x^n+(\text{低次项}),\quad g=b x^m+(\text{低次项}), \qquad\text{其中~}a \neq 0, b \neq 0.
  \]
  \pause
  此时，$f$可写为
  \[
    f=\frac{a}{b}x^{n-m}g+f_1,
  \]
  显然$\partial f_1<\partial f$ 或 $f_1=0$. 
  \pause
  由归纳假设，$f_1$可写为$f_1=gq_1+r$, 其中$\partial r<\partial g$ 或 $r=0$. 这时有
  \[
    f=\frac{a}{b}x^{n-m}g+gq_1+r=g\left(\frac{a}{b}x^{n-m}+q_1\right)+r.
  \]
  \pause
  这样，令$q=\frac{a}{b}x^{n-m}+q_1$, 则所要求的$q,r$就存在了。
  归纳完毕，从而存在性得证。
\end{proof}

%\begin{proof}
%(1) 中 $q$ 和 $r$ 的存在性可以由上面所说的除法直接得出。 我们用归纳法的语言来叙述。
%
%如果 $f=0$, 取 $q=r=0$ 即可。
%
%以下设 $f \neq 0$. 令 $f, g$ 的次数分别为 $n, m$. 对 $f$ 的次数 $n$ 作 (第二) 数学归纳法。 假设当任何 $f$ 的次数小于 $n$ 时， $q, r$ 的存在已证。 现来看次数为 $n$ 的情形。
%
%当 $n<m$ 时，显然取 $q=0, r=f,(1)$ 式成立。
%
%下面讨论 $n \geqslant m$ 的情形。 令 $a x^{n}, b x^{m}$ 分别是 $f, g$ 的首项， 显然 $b^{-1} a x^{n-m} g$ 与 $f$ 有相同的首项，因而多项式
%\[
%f_{1}=f-b^{-1} a x^{n-m} g
%\]
%的次数小于 $n$ 或为零多项式。 对于后者， 取 $q=b^{-1} a x^{n-m}, r=0$; 对于前者， 由归纳假设，对 $f_{1}, g$ 有 $q_{1}, r_{1}$ 存在使
%\[
%f_{1}=q_{1} g+r_{1},
%\]
%其中 $\partial\left(r_{1}\right)<\partial(g)$ 或者 $r_{1}=0$. 于是
%\[
%f=\left(q_{1}+b^{-1} a x^{n-m}\right) g+r_{1},
%\]
%也就是说， 有 $q=q_{1}+b^{-1} a x^{n-m}, r=r_{1}$ 使
%\[
%f=q g+r
%\]
%成立。由归纳法原理，对任意的 $f, g \neq 0, q, r$ 的存在性就证明了。
%
%下面来证唯一性。设另有多项式 $q^{\prime}, r^{\prime}$ 使
%\[
%f=q^{\prime} g+r^{\prime},
%\]
%其中 $\partial\left(r^{\prime}\right)<\partial(g)$ 或者 $r^{\prime}=0$. 于是
%\[
%q g+r=q^{\prime} g+r^{\prime},
%\]
%即
%\[
%\left(q-q^{\prime}\right) g=r^{\prime}-r .
%\]
%如果 $q \neq q^{\prime}$, 又据假设 $g \neq 0$, 那么 $r^{\prime}-r \neq 0$, 且有
%\[
%\partial\left(q-q^{\prime}\right)+\partial(g)=\partial\left(r^{\prime}-r\right) .
%\]
%但是
%\[
%\partial(g)>\partial\left(r^{\prime}-r\right),
%\]
%所以上式不可能成立。这就证明了 $q=q^{\prime}$, 因此 $r=r^{\prime}$. 
%\end{proof}
\end{frame}

\begin{frame}
  \begin{proof}[续]
    再证唯一性。设$f$可写为$f=gq+r=gq'+r'$, 其中
    $\partial r'<\partial g$ 或 $r'=0$, $\partial r<\partial g$ 或 $r=0$.
    \pause
    那么$g(q-q')=r'-r$. 若 $q'\neq q$, 
    则$g\neq 0$和$q-q'\neq 0$表明$r-r'\neq 0$, 即$r\neq r'$. 此时，我们有
  \[
    \partial g+\partial (q-q')=\partial (r'-r)<\partial g,
  \]
  矛盾了。
\pause
  只有$q'=q$. 进而$r=r'$.
  唯一性证毕。
  \end{proof}
\pause
\begin{example}
  设$f=3x^4+x^3+x+3, g=2x^2+x+1\in \QQ[x]$. 
  下面我们通过长除法来得到$g$除$f$的商和余式，这个过程是在不断地消首项，直到余下的多项式的次数小于$g$的次数或为$0$：
  \pause
  {\small
\setlength{\tabcolsep}{2pt}
\renewcommand{\arraystretch}{1.5}
  \[
    \begin{tabular}{RRRR|RRRRRR|RRRR}
      g= & 2x^2 & +x & +1 & f= & 3x^4 & +x^3 &  & +x & +3 & q= & \frac{3}{2}x^2 & -\frac{1}{4}x & -\frac{5}{8}\\
      & & & & & 3x^4 & +\frac{3}{2}x^3 & +\frac{3}{2}x^2 & & & & & & \\
      \cline{5-10}
      & & & & & & -\frac{1}{2}x^3 & -\frac{3}{2}x^2 & +x & +3 & & & \\
      & & & & & &-\frac{1}{2}x^3 & -\frac{1}{4}x^2 & -\frac{1}{4}x &&&&\\
      \cline{5-10}
      & & & & & & & -\frac{5}{4}x^2 & +\frac{5}{4}x& +3 & & & \\
      & & & & & & &  -\frac{5}{4}x^2 & -\frac{5}{8}x & -\frac{5}{8} &&&\\
      \cline{5-10}
      & & & & & & & r=& \frac{15}{8}x & +\frac{29}{8}
    \end{tabular}
  \]
}
%  \begin{equation}\label{0F5}
%    \begin{array}{r@{\hspace{12pt}}lrrrrrrrrrr}
%         & && &  \frac{3}{2}x^2 & -\frac{1}{4}x & -\frac{5}{8}  \\
%      \cline{2-7}
%      2x^2 +x  +1 & \big)&  3x^4 & +x^3 &  & +x & +3 \\
%       &  & 3x^4 & +\frac{3}{2}x^3 & +\frac{3}{2}x^2  \\
%      \cline{3-7}
%      & & & -\frac{1}{2}x^3 & -\frac{3}{2}x^2 & +x & +3  \\
%      &  & &-\frac{1}{2}x^3 & -\frac{1}{4}x^2 & -\frac{1}{4}x &&&&\\
%      \cline{4-7}
%      & & & & -\frac{5}{4}x^2 & +\frac{5}{4}x & +3 & & & \\
%      & & & &  -\frac{5}{4}x^2 & -\frac{5}{8}x & -\frac{5}{8} &&&\\
%      \cline{5-7}
%      &  & & & & \frac{15}{8}x & +\frac{29}{8}
%    \end{array}
%  \end{equation}
  故
  \[
    3x^4+x^3+x+3=(2x^2+x+1)\left(\frac{3}{2}x^2-\frac{1}{4}x-\frac{5}{8}\right)+\left(\frac{15}{8}x+\frac{29}{8}\right).
  \]
\end{example}


\end{frame}

\begin{frame}
  除式形如$x-a$时，我们可以用一种紧凑的方式把长除法写出来，即所谓的\emph{综合除法}。
  \pause
  给定多项式$f=a_nx^n+a_{n-1}x^{n-1}+\cdots+a_1x+a_0\in P[x]$和$a\in P$, 
  要得到$x-a$除$f$的商和余式，我们可以如下进行：
  \[
       \begin{array}{rrrrrrrrr}
          \cline{4-8}
          a&  & & a_n & a_{n-1} & \cdots & a_{1} & a_0\\
          & (+)  & & & ab_{n-1} &   \cdots &ab_{1}  & ab_0 \\
           \cline{4-8}
           &&& b_{n-1} & b_{n-2} & \cdots & b_{0}  & b_{-1}
       \end{array}
  \]
  其中$b_{n-1}=a_n$, $n-2\geqslant i\geqslant -1$时
  $b_i$如下递归地得到$b_{i}=a_{i+1}+ab_{i+1}$. 
  \pause
  这时，我们有$x-a$除$f$的商和余分别为
  \[
    q=b_{n-1}x^{n-1} + b_{n-2}x^{n-2}+\cdots + b_0, \quad  r=b_{-1}.
  \]
  这个很容易直接验证。
\pause
\begin{example}
  令 $f=2x^5-5x^3-8x, g=x+3$. 要得到$g$除$f$的商和余式，执行综合除法如下：
  \[
       \begin{array}{rrrrrrrrrr}
          \cline{3-8}
          -3 & & 2 & 0 & -5 & 0 & -8 & 0\\
          & & & -6 &  18 & -39 & 117 & -327 \\
           \cline{3-8}
           && 2  & -6 & 13 & -39 & 109 & -327
       \end{array}
  \]
  这样$f=gq+r$, 其中$q=2x^4-6x^3+13x^2-39x+109$, $r=-327$.
\end{example}

\end{frame}

\begin{frame}{数学归纳法}
  下面这种数学归纳法 (第一数学归纳法) 的形式大家应该是熟悉的：
  \begin{block}{数学归纳法}
给定一组 (以正整数为指标的) 断言 $P(1), P(2), \cdots,$ 假设
      \begin{itemize}
        \item $P(1)$成立；
        \item 对任意的$n>1$, 若$P(n-1)$成立，则$P(n)$成立。(``$P(n-1)$成立''称为\emph{归纳假设}。)
      \end{itemize}
      那么所有断言$P(n)$都成立。
  \end{block}
  此数学归纳法要求我们证明$P(1)$成立以及$P(n)$ ($n>1$) 在归纳假设下成立。

数学归纳法的另一种形式如下（也称为\emph{完全的数学归纳法}或\emph{第二数学归纳法}):
\begin{block}{数学归纳法} 给定一组 (以正整数为指标的) 断言 $P(1), P(2), \cdots,$ 假设
      \begin{itemize}
        \item 对任意的正整数$n$, 若$P(k)$对任意的正整数$k<n$成立，则$P(n)$成立。
          (``$P(k)$对任意的正整数$k<n$成立''称为\emph{归纳假设}。)
      \end{itemize}
      那么所有断言$P(n)$都成立。
  \end{block}
  所以完全的数学归纳法要求我们在该归纳法的归纳假设下证明$P(n)$成立。
  $n=1$时由于没有比$1$小的正整数，归纳假设为空假设，故$P(1)$成立包含在我们的条件中；
  如此，我们的证明中一定包含了$P(1)$的证明。

 \end{frame}

\begin{frame} 
  有时，我们的断言自然地以非负整数为指标，归纳法原理还是一样的，只不过需要我们变换下指标。


  上面对带余除法的存在性的证明用的是完全的数学归纳法。令$f\neq0$. 我们对$\partial f$归纳时，
  我们相当于把要证明的拆成了如下一组 (以非负整数为指标的) 断言：$P(0), P(1), \ldots$, 
  其中$P(n)$为

  \begin{quote}
 次数为$n$的多项式$f$总可写为$f=gq+r$, 其中$q,r\in P[x]$且$r$满足
      $\partial r<\partial g$或$r=0$.
  \end{quote}

  此时的归纳假设为

  \begin{quote}
对 (给定的$n$和) 任意的非负整数$k<n$, $P(k)$成立，即
      次数小于$n$的非零多项式$f$总可写为$f=gq+r$, 其中$q,r\in P[x]$且$r$满足
      $\partial r<\partial g$或$r=0$.
  \end{quote}

  我们要做的事情就是对任意的非负整数$n$ (作为次数), 在归纳假设下证明$P(n)$,
  进而数学归纳法告诉我们所有的$P(n)$都成立，从而证明了非零多项式$f$ (除以非零多项式$g$) 都有带余除法。
  证明中我们分了两种情况：
  $\partial f< \partial g$, $\partial f\geqslant \partial g$.
  第一种情形下的证明很直接，我们不必使用归纳假设；第二种我们需要用归纳假设。

\begin{proof*}[完全的数学归纳法的有效性的证明]
  我们反证。令$S=\left\{ n\mid \text{$P(n)$不成立} \right\}$. 
  若某些$P(n)$不成立，或者说，$S$非空，则可取最小的$n\in S$, 相应地，$P(n)$不成立。
    $n$的最小性表明$k<n$时$P(k)$都成立。这样根据我们的假设，$P(n)$成立，矛盾了。
\end{proof*}
\end{frame}

\begin{frame}{整除}
  \begin{definition}%定义5 
    称数域 $P$ 上的多项式 $g$ \emph{整除} $f$, 如果有数域 $P$ 上的多项式 $h$ 使等式
$f=g h$
成立。
\pause
我们用 ``$g \mid f$'' 表示 $g$ 整除 $f$, 用 ``$g \nmid f$'' 表示 $g$ 不能整除 $f$.
\pause
当 $g \mid f$ 时， $g$ 就称为 $f$ 的\emph{因式}或\emph{因子}， $f$ 称为 $g$ 的\emph{倍(式)}。
\end{definition}

\pause
当 $g \neq 0$ 时，带余除法给出了整除性的一个判别法。

\begin{theorem}%定理1 
  对于$f, g\in P[x]$, 其中 $g \neq 0$, $g \mid f$的充分必要条件是 $g$ 除 $f$ 的余式为零。
\end{theorem}
\pause
\begin{proof}
如果 $r=0$, 那么 $f=q g$, 即 $g \mid f$.
反过来，如果 $g \mid f$,那么
$f=q g=q g+0,$
即 $r=0.$
\end{proof}

\pause
带余除法中 $g$ 必须不为零， 但 $g \mid f$ 中 $g$ 可以为零。 这时 $f=g h=0 \cdot h=0$.

\pause
当 $g \mid f$ 时， 如 $g \neq 0, g$ 除 $f$ 所得的商 $q$ 有时也用
$\frac{f}{g}$
来表示。

\pause
由定义还可看出， 任一个多项式 $f$ 一定整除它自身 (整除的自反性)， 即 $f \mid f$, 因为 $f=1 \cdot f$; 
\pause
任一个多项式 $f$ 都整除零多项式 $0$, 因为 $0=0 \cdot f$; 
\pause
零次多项式， 也就是非零常数，能整除任一个多项式， 因为当 $a\in P^*$ 时， $f=a\left(a^{-1} f\right)$.
这里$P^*$表示$P$中所有非零数的集合。
\end{frame}

\begin{frame}
下面介绍整除性的几个常用的性质：
\begin{observation*}
  \begin{enumerate}
    \item (整除的互伴性) 如果 $f\mid g, g\mid f$, 那么 $f=c g$, 其中 $c\in P^*$. 
        \pause
      \item (整除的传递性) 如果 $f\mid g, g\mid h$, 那么 $f \mid h$.
        \pause
      \item 如果 $f \mid g_{i}$, $u_i\in P[x]$, $i=1,2, \cdots, r$, 那么
            $f \mid\left(u_{1} g_{1}+u_{2} g_{2}+\cdots+u_{r} g_{r}\right).$
  \end{enumerate}
\end{observation*}
通常，$u_{1} g_{1}+u_{2} g_{2}+\cdots+u_{r} g_{r}$ 称为多项式 $g_{1}, g_{2}, \cdots$, $g_{r}$ 的一个（多项式系数的线性）\emph{组合}。
\pause
\begin{proof}
(1) 事实上， 由 $f \mid g$ 有 $g=h_{1} f$, 由 $g \mid f$ 有 $f=h_{2} g$.于是
\[
f=h_{1} h_{2} f .
\]
如果 $f$ 为零， 那么 $g$ 也为零， 结论显然成立。 如果 $f \neq 0$, 那么消去 $f$ 就有
\[
h_{1} h_{2}=1,
\]
从而 $\partial\left(h_{1}\right)+\partial\left(h_{2}\right)=0$. 由此即得
\[
\partial\left(h_{1}\right)=\partial\left(h_{2}\right)=0 .
\]
这就是说 $h_{2}$ 是一非零常数。 
\end{proof}
\end{frame}

\begin{frame}

\begin{proof}[续]
(2) 显然， 由
\[
g=g_{1} f, \quad h=h_{1} g,
\]
即得
\[
h=\left(h_{1} g_{1}\right) f .
\]

(3) 由 $g_{i}=h_{i} f, i=1,2, \cdots, r$, 即得
\[
u_{1} g_{1}+u_{2} g_{2}+\cdots+u_{r} g_{r} 
=  \left(u_{1} h_{1}+u_{2} h_{2}+\cdots+u_{r} h_{r}\right) f . 
\]
\end{proof}
\pause
由以上的性质可以看出， 多项式 $f$ 与它的任一个非零常数倍 $c f$ ($c \in P^*$) 有相同的因式， 也有相同的倍式。 因之，在多项式整除性的讨论中， $f$ 常常可以用 $c f$ 来代替。
\pause
\begin{observation*}
两个多项式之间的整除关系不因为系数域的扩大而改变，因为带余除式不随域的扩大而改变。 
\end{observation*}
\pause
\begin{proof}
  令 $f, g\in P[x]$, $\bar{P}$ 是包含 $P$ 的一个较大的数域。 
当然， $f$, $g$ 也可以看成是 $\bar{P}[x]$ 中的多项式。从带余除法可以看出，不论把 $f, g$ 看成是 $P[x]$ 中或者是 $\bar{P}[x]$ 中的多项式， 用 $g$ 去除 $f$ 所得的商式及余式都是一样的。 因此， 如果在 $P[x]$ 中 $g$ 不能整除 $f$, 那么在 $P[x]$ 中， $g$ 也不能整除 $f$.
\end{proof}
\end{frame}

\begin{frame}{小结}
  \begin{enumerate}
    \item 具体的多项式的带余除法如何实现? (长除法)
    \item 何为整除？有哪些性质？
    \item 基域扩大时，带余除式和整除关系会如何？
  \end{enumerate}
\end{frame}
